package custom;

public class CustomSort {
    /**
     * 选择法排序
     *
     * @param array 排序数组
     */
    public static void select(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int tempIndexMin = i;
            for (int j = i + 1; j < array.length; j++)
                if (array[tempIndexMin] > array[j])
                    tempIndexMin = j;
            if (tempIndexMin != i) {
                int temp = array[i];
                array[i] = array[tempIndexMin];
                array[tempIndexMin] = temp;
            }
        }
    }

    /**
     * 冒泡法排序
     *
     * @param array 排序数组
     */
    public static void bubble(int[] array) {
        for (int i = 0; i < array.length - 1; i++)
            for (int j = array.length - 1; j > i; j--)
                if (array[j - 1] < array[j]) {
                    int temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                }
    }

    /**
     * 插入法排序
     *
     * @param array 排序数组
     */
    public static void insert(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int temp = array[i];
            int j = i - 1;
            while (j >= 0 && array[j] > temp)
                array[j + 1] = array[j--];
            array[j + 1] = temp;
        }
    }

    protected static int partition0(int[] array, int left, int right) {
        int base = array[left], start = left, end = right;
        while (start < end) {
            while (start < end && array[end] >= base)
                end--;
            while (start < end && array[start] <= base)
                start++;
            if (start < end) {
                int temp = array[start];
                array[start] = array[end];
                array[end] = temp;
            }
        }
        array[left] = array[start];
        array[start] = base;
        return start;
    }

    public static int partition1(int[] array, int left, int right) {
        int base = array[left], start = left, end = right + 1;
        while (true) {
            while (array[++start] < base)
                if (start == right)
                    break;
            while (array[--end] >= base)
                if (end == left)
                    break;
            if (start >= end)
                break;
            int temp = array[start];
            array[start] = array[end];
            array[end] = temp;
        }
        array[left] = array[end];
        array[end] = base;
        return end;
    }

    public static int partition2(int[] array, int left, int right) {
        int base = array[left], start = left, end = right;
        while (start != end) {
            while (start < end && array[end] >= base)
                end--;
            if (start < end)
                array[start++] = array[end];
            while (start < end && array[start] <= base)
                start++;
            if (start < end)
                array[end--] = array[start];
        }
        array[start] = base;
        return start;
    }

    public static int partition3(int[] array, int left, int right) {
        int base = array[left], start = left, end = left + 1;
        while (end <= right) {
            if (array[end] <= base) {
                start++;
                if (start != end) {
                    int temp = array[start];
                    array[start] = array[end];
                    array[end] = temp;
                }
            }
            end++;
        }
        array[left] = array[start];
        array[start] = base;
        return start;
    }

    public static void quick(int[] array, int left, int right) {
        if (left < right) {
            int index = partition3(array, left, right);
            quick(array, left, index - 1);
            quick(array, index + 1, right);
        }
    }

    public static void quick(int[] array) {
        quick(array, 0, array.length - 1);
    }
}